package org.sn.jdish.algorithm.sort;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 排序工具
 * 
 * @author snzigod@hotmail.com
 *
 */
public class SortUtil {

	/**
	 * 冒泡排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] bubbleSort(int[] array) {
		int len = array.length;
		int temp;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len - 1 - i; j++) {
				if (array[j] > array[j + 1]) {
					temp = array[j + 1];
					array[j + 1] = array[j];
					array[j] = temp;
				}
			}
		}
		return array;
	}

	/**
	 * 选择排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] selectionSort(int[] array) {
		int len = array.length;
		int minIndex, temp;
		for (int i = 0; i < len - 1; i++) {
			minIndex = i;
			for (int j = i + 1; j < len; j++) {
				if (array[j] < array[minIndex]) {
					minIndex = j;
				}
			}
			temp = array[i];
			array[i] = array[minIndex];
			array[minIndex] = temp;
		}
		return array;
	}

	/**
	 * 插入排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] insertSort(int[] array) {
		int len = array.length;
		int preIndex, cur;
		for (int i = 1; i < len; i++) {
			preIndex = i - 1;
			cur = array[i];
			while (preIndex >= 0 && array[preIndex] > cur) {
				array[preIndex + 1] = array[preIndex];
				preIndex--;
			}
			array[preIndex + 1] = cur;
		}
		return array;
	}

	/**
	 * 希尔排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] shellSort(int[] array) {
		int dk = array.length / 2;
		while (dk >= 1) {
			for (int i = dk; i < array.length; i++) {
				if (array[i] < array[i - dk]) {
					int j;
					int x = array[i];
					array[i] = array[i - dk];
					for (j = i - dk; j >= 0 && x < array[j]; j = j - dk) {
						array[j + dk] = array[j];
					}
					array[j + dk] = x;
				}
			}
			dk /= 2;
		}
		return array;
	}

	/**
	 * 归并排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] mergeSort(int[] array) {
		return mergeSort(array, 0, array.length - 1);
	}

	/**
	 * 归并
	 * 
	 * @param array
	 * @param left
	 * @param right
	 * @return
	 */
	private static int[] mergeSort(int[] array, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			// 左边
			mergeSort(array, left, mid);
			// 右边
			mergeSort(array, mid + 1, right);
			// 左右合并
			merge(array, left, mid, right);
		}
		return array;
	}

	/**
	 * 归并
	 * 
	 * @param array
	 * @param left
	 * @param mid
	 * @param right
	 */
	private static void merge(int[] array, int left, int mid, int right) {
		int[] temp = new int[right - left + 1];
		int i = left;
		int j = mid + 1;
		int k = 0;
		// 把较小的数先移到新数组中
		while (i <= mid && j <= right) {
			if (array[i] < array[j]) {
				temp[k++] = array[i++];
			} else {
				temp[k++] = array[j++];
			}
		}
		// 把左边剩余的数移入数组
		while (i <= mid) {
			temp[k++] = array[i++];
		}
		// 把右边边剩余的数移入数组
		while (j <= right) {
			temp[k++] = array[j++];
		}
		// 把新数组中的数覆盖nums数组
		for (i = 0; i < temp.length; i++) {
			array[i + left] = temp[i];
		}
	}

	/**
	 * 快速排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] quickSort(int[] array) {

		return array;
	}

	/**
	 * 堆排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] heapSort(int[] array) {

		return array;
	}

	/**
	 * 计数排序
	 * 
	 * @param array
	 * @param maxValue
	 * @return
	 */
	public static int[] countingSort(int[] array, int maxValue) {
		int sortIndex = 0;
		int[] bucket = new int[maxValue + 1];
		for (int i = 0; i < array.length; i++) {
			bucket[array[i]]++;
		}
		for (int i = 0; i < bucket.length; i++) {
			while (bucket[i] > 0) {
				array[sortIndex++] = i;
				bucket[i]--;
			}
		}
		return array;
	}

	/**
	 * 桶排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] bucketSort(int[] array) {

		return array;
	}

	/**
	 * 基数排序
	 * 
	 * @param array
	 *            待排序数组
	 * @param radix
	 *            基数
	 * @param digit
	 *            位数
	 * @return 已排序数组
	 */
	public static int[] radixSort(int[] array, int radix, int digit) {
		Queue<Integer>[] digitQueue = (LinkedList<Integer>[]) (new LinkedList[radix]);

		for (int i = 0; i < radix; i++) {
			digitQueue[i] = (Queue<Integer>) (new LinkedList<Integer>());
		}

		for (int i = 0; i < digit; i++) {
			for (int j = 0; j < array.length; j++) {
				String temp = String.valueOf(array[j]);
				if (temp.length() > i) {
					digitQueue[Character.digit(temp.charAt(temp.length() - 1 - i), radix)].add(array[j]);
				} else {
					digitQueue[0].add(array[j]);
				}
			}

			int num = 0;
			for (int j = 0; j < radix; j++) {
				while (!(digitQueue[j]).isEmpty()) {
					array[num] = digitQueue[j].remove();
					num++;
				}
			}
		}
		return array;
	}

}
